package com.leetcode;


import java.util.NavigableMap;
import java.util.TreeMap;

/**
 * 1163. 按字典序排在最后的子串 (困难)
 * 给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。
 */
public class LeetCode1163 {

    public static void main(String[] arg0) {
        String testStr = "abab";
        System.out.println("排在最后的那个子串 = " + lastSubstring(testStr));


        // 对有序TreeMap的测试，不论放入的先后，键总是会排序
        TreeMap<Integer, String> ziMuBiao = new TreeMap<>();
        ziMuBiao.put(4, "D");
        ziMuBiao.put(1, "A");
        ziMuBiao.put(2, "B");
        ziMuBiao.put(3, "C");
        NavigableMap desMap = ziMuBiao.descendingMap();
        System.out.println("ziMuBiao:" + ziMuBiao);
        System.out.println("倒叙treeMap.descendingMap():" + desMap);
    }

    /**
     * 只考虑 s 的后缀子字符串，就是的终点下标一定是 s 的结尾
     * 所以只要确定结果的起点是哪里n
     */
    public static String lastSubstring(String s) {
        int i = 0; // 记录结果起点的位置，一开始设为最开始
        int j = 1; // 待比较子字符串的起点

        while (j < s.length()) {
            int k = 0;
            while (j + k < s.length() && s.charAt(i + k) == s.charAt(j + k)) { // 子串比较时前面有一部分相同
                k++;
            }

            if (j + k < s.length() && s.charAt(i + k) < s.charAt(j + k)) {
                int t = i;
                i = j;
                j = Math.max(j + 1, t + k + 1);
            } else {
                j = j + k + 1;
            }

            // 这么简单的比较 "cacacb" 会过不了，就是缺少了 ca 和 cb 组合起来的比较
            /*if (s.charAt(i) < s.charAt(j)) {
                i = j;
                j = i + 1;
            } else {
                j++;
            }*/
        }

        return s.substring(i);
    }


}
